
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<pair<int, int>> a;
vector<vector<int>> b(100100);
vector<int> visit(100100);
void dfs(int x) {
    cout << x << " ";
    visit[x] = true;
    for(auto s : b[x]) {
        if(!visit[s]) {
            dfs(s);
        }
    }
}
void bfs(int x) {
    queue<int> q;
    q.push(x);
    visit[x] = true;
    while(!q.empty()) {
        int temp = q.front();
        q.pop();
        cout << temp << " ";
        for(auto& s : b[temp]) {
            if(!visit[s]) {
                q.push(s);
                visit[s] = true;
            } 
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        a.push_back({x, y});
    }
    sort(a.begin(), a.end());
    for(auto& [l, r] : a) {
        b[l].push_back(r);
    }
    dfs(1);
    fill(visit.begin(), visit.end(), 0);
    cout << endl;
    bfs(1);
    return 0;
}